
import java.util.*;

/**
 * PostfixEvaluator this modification of our stack example uses a 
 * stack to create an expression tree from a VALID integer postfix expression 
 * and then uses a recursive method from the ExpressionTree class to 
 * evaluate the tree.
 * 
 * build function added and extract the evaluate function, return exception if the input is not valid for an expression tree 
 * 
 * @author Color Lee
 */
public class TreeEvaluator    
{
    private Stack<ExpressionTree> treeStack;
    private Stack<LinkedBinaryTree<String>> stepTreeStack;
    private ArrayUnorderedList<Variable> listV;
    private boolean validTree;
    private int variableCount;
    
    /**
     * Sets up this evaluator by creating a new stack.
     */
    public TreeEvaluator()
    {
        treeStack = new Stack<ExpressionTree>();
        stepTreeStack = new Stack<LinkedBinaryTree<String>>();
        validTree = true;
        variableCount = 0;
    }

    /**
     * Retrieves and returns the next operand off of this tree stack.
     *
     * @param treeStack  the tree stack from which the operand will be returned
     * @return the next operand off of this tree stack
     */
    private ExpressionTree getOperand(Stack<ExpressionTree> treeStack)
    {
        ExpressionTree temp = null;
        if (!treeStack.isEmpty()){
        	temp = treeStack.pop();
        }
        return temp;
    }
    
    /**
     * Build the tree according to the expression and return a boolean value for valid tree of not
     *
     * @param expression string representation of a postfix expression
     */
    public void build(String expression)
    {
    	listV = new ArrayUnorderedList<Variable>(expression.length());
        ExpressionTree operand1, operand2;
        char character;
        int count = 0;
        variableCount = 0;
        
        while (count < expression.length())
        {
        	character = expression.charAt(count);
            
            if ((character == '+') || (character == '-') || (character == '*') || 
                 (character == '/'))
            {
        		operand1 = getOperand(treeStack);
                operand2 = getOperand(treeStack);
                if (operand1 != null && operand2 != null){
                	treeStack.push(new ExpressionTree 
                            (new ExpressionTreeOp(1,character,new Variable(" ")), operand2, operand1));
                }else{
            		validTree = false;
            		break;
                }            	
            }
            else
            {
            	if (Character.isLetter(character)){
            		Variable temp = checkVariable(listV, character);
            		if (temp == null){
            			temp = new Variable(character+"");
            			listV.addToRear(temp);
                		variableCount++;
            		}
            		treeStack.push(new ExpressionTree(new ExpressionTreeOp(2,' ',temp), null, null));
            	}else{
            		treeStack.push(new ExpressionTree(new ExpressionTreeOp(2,' ',new Variable(character+"", Integer.parseInt(character+""))), null, null));
            	}
            }
            count++;            
        }
        if (treeStack.size() > 1) validTree = false;
        if (validTree) sortlistV();
    }
    
    /**
     * Build the step tree according to the computation step in evaluate() function
     */
    public void buildStepTree(){
    	evaluate();
    	ArrayUnorderedList<Step> stepList = (treeStack.peek()).getComputerStepList();
    	LinkedBinaryTree<String> operand1, operand2;
    	int count = 0;

    	while (count < stepList.rear){
    		
    		Step temp = stepList.get(count);
    		Dependent tempDependent = temp.getDependent();
    		
    		if (tempDependent != null){
    			operand1 = stepTreeStack.pop();
    			switch(tempDependent.getDirection()){
    			case Dependent.isLeft:
    				stepTreeStack.push(new LinkedBinaryTree<String>(temp.toStringShortForm(),
							    								    operand1,
							    								    new LinkedBinaryTree<String>(Integer.toString(temp.getOperand2()))
							    								    )
    								   );
    				break;
    			case Dependent.isRight:
    				stepTreeStack.push(new LinkedBinaryTree<String>(temp.toStringShortForm(),
							    								    new LinkedBinaryTree<String>(Integer.toString(temp.getOperand1())),
							    								    operand1
							    								    )
    								   );
    				break;
    			case Dependent.isLeftAndRight:
    				operand2 = stepTreeStack.pop();
    				stepTreeStack.push(new LinkedBinaryTree<String>(temp.toStringShortForm(),
																    operand2,
																    operand1
																    )
										);
    				break;
    			}
    		}else{
    			stepTreeStack.push(new LinkedBinaryTree<String>(temp.toStringShortForm(), 
							    							    new LinkedBinaryTree<String>(Integer.toString(temp.getOperand1())),
							    							    new LinkedBinaryTree<String>(Integer.toString(temp.getOperand2()))
							    							   )
    							  );
    		}    		
    		count++;
    	}
    }
    
    /**
     * Function for updating all the variable character included in the string expression.
     * It will prompt all the variable character letter included for the value
     */
    public void updateVariable(){
    	IO io = new IO();
    	for (int i = 0; !listV.isEmpty() && i < listV.size(); i++){
    		String c = listV.get(i).getCharacter();
    		listV.get(i).setInteger(
    				io.showQuestionInt(c + ": ")
    				);
    	}
    }
    
    /**
     * Sort all the variables included in string expression to be ordered in ascending order
     */
    private void sortlistV(){
    	for (int i = 1; !listV.isEmpty() && i < variableCount; i++){
    		String key = listV.get(i).getCharacter();
    		int position = i;
    		while (position > 0 && listV.get(position-1).getCharacter().compareTo(key) > 0){
    			listV.addAfter(listV.get(position-1), listV.get(position));
    			listV.remove(listV.get(position-1));
    			position--;
    		}
    	}
    }
    
    /**
     * 
     * @param listV existing variables list
     * @param character variable character to check
     * @return the Variable class if the variable exists, otherwise return null
     */
    private Variable checkVariable(ArrayUnorderedList<Variable> listV, char character){
    	for (int i = 0; i < variableCount; i++){
    		if (listV.get(i).getCharacter().equals(character+"" ))
    			return listV.get(i);
    	}
    	return null;
    	
    }
    
    /**
     * Get all the inputed variable characters and the variable values
     * @return Variables characters and value separate by a colon
     */
    public String getVariableList(){
    	String result = "Variable(s):";
    	for (int i = 0; !listV.isEmpty() && i < variableCount; i++){
    		result += " " + listV.get(i).getCharacter() + ":" + listV.get(i).getInteger();
    	}
    	return result;
    }
    
    /**
     * Get the inputed string expression in a post order
     * @return String value of the expression in a post order
     */
    public String getPostfixIncludeVariable(){
    	return "Postfix: " + treeStack.peek().postOrderIncludeVariable(true);
    }
    
    /**
     * Print out the result with description result instead of only the answer
     * @return String value contain the evaluate result
     */
    public String evaulateResult(){
    	return "The evaluation result is: " + evaluate() + "\n";
    }
    
    /**
     *Evaluates the specified postfix expression by evaluating an expression tree. 
     * @return value of the given expression
     */
    public int evaluate(){
    	return (treeStack.peek()).evaluateTree();
    }
    
    /**
     * Evaluates the computation step of evaluating an expression tree
     * @return A list of computation step of the given expression
     */
    public String evaluateStep(){
    	evaluate();
    	return (treeStack.peek()).getComputeStep();
    }
    
    /**
     * Build and return the tree include the computation step of the string expression
     * @return string representing the computation step tree
     */
    public String getStepTree(){
    	buildStepTree();
    	if (stepTreeStack.isEmpty())
    		return getTree();
    	return getStepTree(stepTreeStack.peek().getRootNode(), "");
    }
    
    private String getStepTree(BinaryTreeNode<String> r, String strIndent){
    	if (r == null) return "";
    	String result = "";
    	result += getStepTree(r.getRight(), strIndent+"            ");
    	result += strIndent + r.getElement().toString()+"\n";
    	result += getStepTree(r.getLeft(), strIndent+"            ");
    	return result;
    }
    
    /**
     * Return the fully parenthesize of the expression based on the expression tree
     * @return string value of the fully parenthesize expression
     */
    public String getStepInorder(){
    	buildStepTree();
    	if (!stepTreeStack.isEmpty())
    		return getStepInorder((stepTreeStack.peek()).getRootNode()) + "\n";
    	return treeStack.peek().postOrderIncludeVariable(false) + "\n";
    }
    
    private String getStepInorder(BinaryTreeNode<String> r){
    	if (r == null) return "";
    	String result = "";
    	String operator = "";
    	boolean isStep = r.getElement().toString().indexOf("=") != -1;
    	
    	if (isStep){
    		result += "(" + getStepInorder(r.getLeft());
    		if (r.getElement().toString().indexOf("+") != -1) operator = "+"; 
        	else if (r.getElement().toString().indexOf("*") != -1) operator = "*";
        	else if (r.getElement().toString().indexOf("/") != -1) operator = "/";
        	else if (r.getElement().toString().indexOf("-") != -1) operator = "-";
    		result += operator;
    		result += getStepInorder(r.getRight()) + ")";
    	}else{
    		result += getStepInorder(r.getLeft());
    		result += r.getElement().toString();
    		result += getStepInorder(r.getRight());
    	}
    	
    	return result;
    }
    
    /**
     * Returns the expression tree associated with this postfix evaluator. 
     * @return string representing the expression tree
     */
    public String getTree()
    {
    	if (validTree)
    		return (treeStack.peek()).printTree();
    	else{
    		System.out.print(new IncorrectInputException("Wrong input.").toString());
    		System.exit(0);
    	}
    	return "";
    }
}
